package leo.mystudy.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 删除链表的倒数第N个节点
 *
 * @author chao.li@quvideo.com
 * @date 2018/7/3 16:30
 */
public class RemoveNthNodeFromEndOfList {
    //    给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
//
//    示例：
//
//    给定一个链表: 1->2->3->4->5, 和 n = 2.
//
//    当删除了倒数第二个节点后，链表变为 1->2->3->5.
//    说明：
//
//    给定的 n 保证是有效的。
//
//    进阶：
//
//    你能尝试使用一趟扫描实现吗？
    public ListNode removeNthFromEnd(ListNode head, int n) {
        List<ListNode> list = new ArrayList<>();
        ListNode temp = head;
        while (temp != null) {
            list.add(temp);
            temp = temp.next;
        }
        if (head.next == null) {
            return null;
        }
        if (n == 1) {
            list.get(list.size() - 2).next = null;
            return head;
        }
        if (n == list.size()) {
            return head.next;
        }
        list.get(list.size() - n - 1).next = list.get(list.size() - n + 1);
        return head;
    }

    public static void main(String[] args) {

    }
}
